#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

/**
 * @方法: 把数组下标和元素绑定，按元素值排序。数据为 10^6 或更少，可以考虑
 * nlogn。
 * @时间复杂度: o(nlogn)
 * @空间复杂度: o(n)
 * @评价: 绑定后的数据结构选择：
 *          vector<vector<int>>超时，
 *          int *all[nums.size()]勉强过，
 *          struct pair all[nums.size()] 效率很高
 *          可能的原因，vector 和 int *all[nums.size()]
 * 都是动态分配空间，也许会使得排序时间增加。
 */
bool containsNearbyDuplicate(vector<int>& nums, int k) {
    typedef struct pair {
        int pos;
        int val;
    } Pair;

    Pair all[nums.size()];

    if (nums.size() == 1) return false;

    for (int i = 0; i < nums.size(); i++) {
        // 0: 下标， 1：值
        all[i].pos = i;
        all[i].val = nums[i];
    }

    sort(all, all + nums.size(), [](Pair x, Pair y) {
        if (x.val == y.val) return x.pos < y.pos;
        return x.val < y.val;
    });

    for (int i = 1; i < nums.size(); ++i) {
        if (all[i].val == all[i - 1].val && all[i].pos - all[i - 1].pos <= k) {
            return true;
        }
    }
    return false;
}

/**
 * @方法: 哈希set + 滑动窗口。
 * @时间复杂度: o(n)
 * @空间复杂度: o(k)
 * @评价:  哈希集合的操作时间都可认为是 o(1)
 */
bool containsNearbyDuplicate2(vector<int>& nums, int k) {
    unordered_set<int> window;

    for (int i = 0; i <= k && i < nums.size(); i++) {
        if (window.find(nums[i]) != window.end()) {
            return true;
        } else {
            window.insert(nums[i]);
        }
    }

    for (int i = k + 1; i < nums.size(); i++) {
        window.erase(nums[i - k - 1]);
        if (window.find(nums[i]) != window.end()) {
            return true;
        } else {
            window.insert(nums[i]);
        }
    }
    return false;
}

/**
 * @方法: 哈希 map，键：数组元素，值：数组元素最近一次出现的下表
 * @时间复杂度: o(n)
 * @空间复杂度: o(n)
 * @评价: 哈希集合的操作时间都可认为是 o(1)
 */
bool containsNearbyDuplicate1(vector<int>& nums, int k) {
    unordered_map<int, int> v2p;
    for (int i = 0; i < nums.size(); ++i) {
        auto it = v2p.find(nums[i]);
        if (it != v2p.end() && abs(it->second - i) <= k) {
            return true;
        } else {
            v2p[nums[i]] = i;
        }
    }
    return false;
}